package org.example.basic_sort;

/**
 * 快速排序
 * 时间复杂度：O(nlogn)
 * 空间复杂度：O(logn)
 * 稳定性：不稳定
 */
public class Code08_quickSort {
    public static void quickSort(int[] arr) {
        if(arr == null || arr.length < 2) {
            return;
        }
        quickSort(arr,0, arr.length-1);
    }

    public static void quickSort(int[] arr,int L ,int R) {
        if(L < R) {
            swap(arr,L + (int)(Math.random()* (R-L + 1)),R);//使R位置的数随机
            int[] p = partition(arr,L,R); //分区
            quickSort(arr,L,p[0] - 1); // 递归左边
            quickSort(arr,p[1] + 1,R); // 递归右边
        }

    }

    // 分区函数 返回左右边界

    public static int[] partition(int[] arr,int L,int R) {
        //荷兰国旗问题
        int less = L - 1; //
        int more = R;
        while(L < more) {
            if(arr[L] < arr[R]) {
                swap(arr,++less,L++); //将小于arr[R]的数放到左边 L指向下一个位置
            } else if (arr[L] > arr[R]) {
                swap(arr,--more,L); //将大于arr[R]的数放到右边 more指向前一个位置
            } else {
                L++; //相同的数，不动
            }
        }
        swap(arr,more,R); //将arr[R]放到分区的中间位置
        return new int[]{less + 1,more}; //返回分区的左右边界
    }
    public static void swap(int[] arr,int i,int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
